package algorithm;

import java.util.*;

/**
 * Definition for a binary tree node.
 **/

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }
    TreeNode(int val) {
        this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right){
       this.val = val;
       this.left = left;
       this.right = right;
    }
}


public class visitOrder {
    //迭代法前序遍历二叉树
    public static List<Integer> preoderTraversal(TreeNode root){
        List<Integer> res = new ArrayList<>();
        if(root == null)
            return res;
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            res.add(node.val);
            if(node.right != null) //右子结点先入栈 才能左-》右
                stack.push(node.right);
            if(node.left != null)
                stack.push(node.left);
        }
        return res;
    }

    // 前序遍历方法2
    public static List<Integer> preOrderTraversal(TreeNode root){
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(!stack.isEmpty() || cur != null) {
            if(cur != null) {
                res.add(cur.val);
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                cur = cur.right;
            }
        }
        return res;
    }

    //中序遍历
    public static List<Integer> inorderTraversal(TreeNode root){
        List<Integer> res = new ArrayList<>();
        if(root == null)
            return res;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root; //用于访问节点
        // cur != null 用于第一次进入循环
        while(cur != null || !stack.isEmpty()){
            if(cur != null){
                stack.push(cur); //将访问的节点放入栈中
                cur = cur.left; //一直访问左子树 直到底部
            }else{
                //如果cur为空，代表上一步访问的左子节点为空，回退弹出栈中节点继续找
                cur = stack.pop(); //栈弹出数据处理
                res.add(cur.val); //中
                cur = cur.right; //右
            }
        }
        return res;
    }

    //后序遍历 反转一下前序遍历的顺序 左子节点先入栈
    public static List<Integer> postOrderTraversal(TreeNode root){
        List<Integer> res = new ArrayList<>();
        if(root == null)
            return res;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            res.add(node.val);
            if(node.left != null) stack.push(node.left);
            if(node.right != null) stack.push(node.left);
        }
        Collections.reverse(res);
        return res;
    }

    //不reverse
    public static List<Integer> postOrderTravel(TreeNode root){
        List<Integer> res = new ArrayList<>();
        if(root == null)
            return res;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if(node != null) {
                stack.push(node);
                stack.push(null);
                if(node.right != null) stack.push(node.right);
                if(node.left != null) stack.push(node.left);
            } else {
                node = stack.pop();
                res.add(node.val);
            }
        }
        return res;
    }

    // 后序遍历统一迭代法
    public List<Integer> postOrder(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> res = new ArrayList<>();
        TreeNode cur = root;
        while(!stack.isEmpty() || cur != null) {
            if(cur != null) {
                stack.push(cur);
                // 倒序添加
                res.add(0, cur.val);
                cur = cur.right;
            } else {
                cur = stack.pop();
                cur = cur.left;
            }
        }
        return res;
    }

    //层序迭代法
    public static List<Integer> levelTraversal(TreeNode root){
        List<Integer> res = new ArrayList<>();
        if(root == null)
            return res;
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        while(!que.isEmpty()){
            TreeNode node = que.poll();
            res.add(node.val);
            if(node.left != null) que.offer(node.left);
            if(node.right != null) que.offer(node.right);;
        }
        return res;
    }

    public static void main(String[] args) {
        TreeNode node4 = new TreeNode(4, null, null);
        TreeNode node3 = new TreeNode(3, null, node4);
        TreeNode node2 = new TreeNode(2, null, node3);
        TreeNode node5 = new TreeNode(5, null, null);
        TreeNode node1 = new TreeNode(1, node2, node5);
        /*
                1
               /  \
              2    5
              \
               3
                \
                 4
         */
        List<Integer> res = visitOrder.inorderTraversal(node1);
        System.out.println(res);
    }
}
